package com.gxc.array;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 3176. 求出最长好子序列 I

 * 给你一个整数数组 nums 和一个 非负 整数 k 。
 * 如果一个整数序列 seq 满足在范围下标范围 [0, seq.length - 2] 中存在 不超过 k 个下标 i
 * 满足 seq[i] != seq[i + 1] ，那么我们称这个整数序列为 好 序列。
 *
 * 请你返回 nums 中 好 子序列的最长长度
 */
public class MaximumLength {

    public static void main(String[] args) {
        System.out.println(handle(new int[]{1}, 2));
    }

    /**
     *
     */
    public static int handle(int[] nums, int k) {
        //已数字 x 结尾的  int[k] 有至多 0...k  个「相邻不同」数对的子序列的最大长度
        Map<Integer, int[]> map = new HashMap<>();

        int[][] dp = new int[k+1][3];
        for (int i = 0; i < nums.length; i++) {
            //以 nums[i] 结尾的数字，有最多  0.。。k 个 相邻不同的  子序列
            int[] kdp = map.computeIfAbsent(nums[i], j -> new int[k + 1]);
            //-----------为什么从 K开始循环，不从0 开始
            //计算 kdp[x][j] 时会用到 kdp[j−1]，然后更新 kdp[j]，可以倒序枚举 j，以避免使用覆盖后的数据
            for (int k1 = k; k1 >= 0; k1--) {
                //如果已经存在以 nums[i] 结尾的子序列， 加上相同的数字， 最大长度+1
                //如果不存在以 nums[i] 结尾的子序列， 以当前数字为第一个数，最大长度+1
                kdp[k1]++;
                if (k1 > 0) {
                    // max  以 n 结尾的最大长度
                    // sMax 不以 n 结尾的最大长度 ???
                    // n 结尾的值
                    int max = dp[k1-1][0], sMax = dp[k1-1][1], n = dp[k1-1][2];
                    //  i!=n?max:sMax   kdp[k1]++; 已经处理  i==n
                    kdp[k1] = Math.max(kdp[k1], (i!=n?max:sMax)+1);
                }

                int v = kdp[k1];
                int[] p = dp[k1];
                if (v > p[0]) {
                    if (i != p[2]) {
                        p[2] = i;
                        p[1] = p[0];
                    }
                    p[0] = v;
                } else if (v > p[1] && v != p[2]) {
                    p[1] = v;
                }
            }
        }
        return dp[k][0];
    }

    /**
     * nums[i][j]
     * nums[i] 结尾组成的最长合法序列中有 j 个数字与其在序列中的后一个数字不相等
     */
    class Solution {
        public int maximumLength(int[] nums, int k) {
            int ans = 0;
            int len = nums.length;
            int[][] dp = new int[len][51];
            for (int i = 0; i < len; i++) {
                Arrays.fill(dp[i], -1);
            }

            for (int i = 0; i < len; i++) {
                dp[i][0] = 1;
                for (int l = 0; l <= k; l++) {
                    for (int j = 0; j < i; j++) {
                        int add = nums[i] != nums[j] ? 1 : 0;
                        if (l - add >= 0 && dp[j][l - add] != -1) {
                            dp[i][l] = Math.max(dp[i][l], dp[j][l - add] + 1);
                        }
                    }
                    ans = Math.max(ans, dp[i][l]);
                }
            }

            return ans;
        }
    }

    class Solution2 {
        public int maximumLength(int[] nums, int k) {
            int len = nums.length;
            Map<Integer, int[]> dp = new HashMap<Integer, int[]>();
            int[] zd = new int[k + 1];

            for (int i = 0; i < len; i++) {
                int v = nums[i];
                dp.putIfAbsent(v, new int[k + 1]);

                int[] tmp = dp.get(v);
                for (int j = 0; j <= k; j++) {
                    tmp[j] = tmp[j] + 1;
                    if (j > 0) {
                        tmp[j] = Math.max(tmp[j], zd[j - 1] + 1);
                    }
                }
                for (int j = 0; j <= k; j++) {
                    zd[j] = Math.max(zd[j], tmp[j]);
                    if (j > 0) {
                        zd[j] = Math.max(zd[j], zd[j - 1]);
                    }
                }
            }
            return zd[k];
        }
    }

    public int maximumLength(int[] A, int k) {
        Map<Integer, Integer>[] dp = new HashMap[k + 1];
        for (int i = 0; i <= k; i++) {
            dp[i] = new HashMap<>();
        }
        int[] res = new int[k + 1];
        for (int a : A) {
            for (int i = k; i >= 0; --i) {
                int v = dp[i].getOrDefault(a, 0);
                v = Math.max(v + 1, (i > 0 ? res[i - 1] + 1 : 0));
                dp[i].put(a, v);
                res[i] = Math.max(res[i], v);
            }
        }
        return res[k];
    }

    class Solution3 {
        public int maximumLength(int[] nums, int k) {
            Map<Integer, int[]> fs = new HashMap<>();
            int[][] records = new int[k + 1][3];
            for (int x : nums) {
                //// 取出以x结尾的长度不超过j的最大子序列长度是多少
                int[] f = fs.computeIfAbsent(x, i -> new int[k + 1]);
                for (int j = k; j >= 0; j--) {
                    //选当前x，并且当前x与前一个相同 或者作为子序列的第一个数
                    f[j]++;
                    if (j > 0) {
                        // 考虑不同
                        int mx = records[j - 1][0], mx2 = records[j - 1][1], num = records[j - 1][2];
                        f[j] = Math.max(f[j], (x != num ? mx : mx2) + 1);
                    }

                    // 更新
                    int v = f[j];// 以x结尾相邻不同对数小于等于j的最大序列长度
                    int[] p = records[j];
                    if (v > p[0]) {
                        if (x != p[2]) {
                            // 之前相邻对数不超过j的最大长度变次小长度。
                            p[2] = x;
                            p[1] = p[0];
                        }
                        p[0] = v;
                    } else if (x != p[2] && v > p[1]) {
                        // 更新次小
                        p[1] = v;
                    }
                }
            }
            return records[k][0];
        }
    }

    class Solution4 {
        public int maximumLength(int[] nums, int k) {
            Map<Integer, int[]> fs = new HashMap<>();
            int[] mx = new int[k + 2];
            for (int x : nums) {
                int[] f = fs.computeIfAbsent(x, i -> new int[k + 1]);
                for (int j = k; j >= 0; j--) {
                    f[j] = Math.max(f[j], mx[j]) + 1;
                    mx[j + 1] = Math.max(mx[j + 1], f[j]);
                }
            }
            return mx[k + 1];
        }
    }


}
